package sorting_algorithms;

/**
 * author :  apurv verma
 * email  :  dapurv5@gmail.com
 */

public class MergeSort {
	
	private static void merge(double A[], int p, int q, int r){
		int n1=q-p+1;
		int n2=r-q;
		double L[]=new double[n1+1];
		double R[]=new double[n2+1];
		int i,j;
		for(i=0;i<n1;i++){
			L[i]=A[p+i];
		}
		for(j=0;j<n2;j++){
			R[j]=A[q+j+1];
		}
		L[n1]=Double.MAX_VALUE;
		R[n2]=Double.MAX_VALUE;
		i=0;j=0;
		for(int k=p;k<=r;k++){
			if(L[i]<R[j]){
				A[k]=L[i];
				i=i+1;       
			}
			else{
				A[k]=R[j];
				j=j+1;
			}
		}
	}
	
	/*
	 * SORTS THE ARRAY A[] OF DOUBLE TYPE BETWEEN THE INDEXES p  AND r INCLUDING p AND r IN ASCENDING ORDER.
	 */
	public static void mergesort(double A[], int p, int r){
		if(p<r){
			int q=(p+r)/2;
			mergesort(A,p,q);
			mergesort(A,q+1,r);
			merge(A,p,q,r);
		}
	}
	
	/*
	 * SORTS INTEGER ARRAYS I[] AND J[] ACCORDING TO DOUBLE ARRAY A[] BETWEEN THE INDEXES p AND r.
	 */
	public static void mergesortAccordingly(double A[],int I[], int J[], int p, int r){
	
		if(p<r){
			int q=(p+r)/2;
			mergesortAccordingly(A,I,J,p,q);
			mergesortAccordingly(A,I,J,q+1,r);
			mergeAccordingly(A,I,J,p,q,r);
		}
	}
	
	private static void mergeAccordingly(double A[],int I[], int J[],int p,int q, int r){
		int n1=q-p+1;
		int n2=r-q;
		double L[]=new double[n1+1];
		double R[]=new double[n2+1];
		
		int LI[]=new int[n1];
		int RI[]=new int[n2];
		
		int LJ[]=new int[n1];
		int RJ[]=new int[n2];
		
		int i,j;
		for(i=0;i<n1;i++){
			L[i]=A[p+i];
			LI[i]=I[p+i];
			LJ[i]=J[p+i];
		}
		for(j=0;j<n2;j++){
			R[j]=A[q+j+1];
			RI[j]=I[q+j+1];
			RJ[j]=J[q+j+1];
		}
		L[n1]=Double.MAX_VALUE;
		R[n2]=Double.MAX_VALUE;
				
		i=0;j=0;
		for(int k=p;k<=r;k++){
			if(L[i]<R[j]){
				A[k]=L[i];
				I[k]=LI[i];
				J[k]=LJ[i];
				i=i+1;       
			}
			else{
				A[k]=R[j];
				I[k]=RI[j];
				J[k]=RJ[j];
				j=j+1;
			}
		}
	}
	
}
